package 中等.分类讨论;

/**
 * Alice 和 Bob 再次设计了一款新的石子游戏。现有一行 n 个石子，每个石子都有一个关联的数字表示它的价值。
 * 给你一个整数数组 stones ，其中 stones[i] 是第 i 个石子的价值。
 * Alice 和 Bob 轮流进行自己的回合，Alice 先手。每一回合，玩家需要从 stones 中移除任一石子。
 * 如果玩家移除石子后，导致 所有已移除石子 的价值 总和 可以被 3 整除，那么该玩家就 输掉游戏 。
 * 如果不满足上一条，且移除后没有任何剩余的石子，那么 Bob 将会直接获胜（即便是在 Alice 的回合）。
 * 假设两位玩家均采用 最佳 决策。如果 Alice 获胜，返回 true ；如果 Bob 获胜，返回 false 。
 * 1 <= stones.length <= 105
 * 1 <= stones[i] <= 104
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/stone-game-ix
 */
public class 石子游戏IX_2029 {

    public static void main(String[] args) {

        int[] stones = {2, 3, 2, 2};
        System.out.println(stoneGameIX(stones));

    }

    /**
     * 价值 总和 可以被 3 整除，那么石子的价值可以用三种类型表示，0,1,2
     * 当玩家没有1,2石子选择的时候，可以选择0，将困境交给另一个玩家
     * 模拟
     * Alice有优先选择权
     * Alice的最优策略：成为多数牌的拥有者
     * Alice 1 Bob 1 Alice 2 Bob 1 Alice 2 -> 显然Alice的牌的个数是第一张1和所有2
     * Alice 2 Bob 2 Alice 1 Bob 2 Alice 1 -> 显然Alice的牌的个数是第一张2和所有1
     * 无论Alice先手选哪个牌，那么它以后的牌都可以被确定了，且和Bob的不重合
     * <p>
     * 加入万能牌0
     * 当万能牌的个数为偶数时，那么每个人都优先选择万能牌，且某种牌的所属者不会被改变，结果和没有万能牌是一样的
     * 当为奇数时,Alice的最优策略：成为少数量的拥有者，选择万能牌0的控制权在自己手里，
     * Alice 1 Bob 0 Alice 1 Bob 2 Alice 1 Bob 2
     * Alice 1 Bob1 Alice 0
     *
     * @param stones
     * @return
     */
    public static boolean stoneGameIX(int[] stones) {
        int[] total = new int[3];
        for (int stone : stones) {  //余数为0,1,2的个数
            total[stone % 3] += 1;
        }
        if (total[0] % 2 == 0) {
            //1,2的牌都没有时，Alice输
            //只存在一种类型的牌，那么=1时，Alice输，>1时，Alice输
            if (total[1] == 0 || total[2] == 0) {
                return false;
            } else {
                return true;
            }
        } else {
            if (total[1] == 0 && total[2] == 0) {  //Alice先手时没有1,2牌选择直接输
                return false;
            }
            if (total[1] == 0 || total[2] == 0) {  //只有一种牌可以选，a 1 b 1 a 0 b输，a 1 b 0 a 1 b输
                if (total[1] <= 2 && total[2] <= 2) {  //加上万能牌总共只有3张牌时，已经没有牌选择，b赢
                    return false;
                } else {
                    return true;
                }
            }
            //Alice想要赢，不能够是正好取出最后一张牌，1 2 2 2
            //-> a 2 b 0 a 2 b 1 a 2 这时2还有一张时，a赢，牌的数量相差必须大于等于3
            return Math.abs(total[2] - total[1]) >= 3 ? true : false;
        }
    }

}